package offer.day10;

public class No14maxMultipleCutting {
    /*
     * 面试题14：剪绳子
     * 题目：给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1且n>1）
     * 		每根绳子的长度记为k[0]，k[1],...,k[m].
     * 		请问k[0]*k[1]*...*k[m]可能的最大乘积是多少？
     * 		例如，当绳子的长度为8时，我们把它分别剪成2、3、3的三段，此时得到的最乘积是18.
     * 		因此，此问题求解的是长度为n的绳子，被分为m段时得到最大乘积，不考虑m值，只求乘积为多少。
     *
     * 思路：第一种方法（动态规划）
     * 		进行循环，f(i)=max{f(j)*f(i-j)}  j=1,...,i/2,一般即可，另一半是对称的，不必计算
     * 		取最大值，从i=1，2，3，。。。逐个增加进行计算将最大值存入一个数组中，方便计算
     *
     *  第二种方法（贪心算法）
     * 		尽可能多的剪出长度为3的绳子，剩下的绳子为4时，则将其分为2+2形式
     * 		先求出有多少个长度为3的，再看剩下的，剩下为1，则和前一个3，变为4，分解为2+2
     * 								    剩下为0，则直接求多少个3相乘
     * 								    剩下为2，则3乘完之后再*2
     *
     * ）
     * */

    public static void main(String[] args) {
        int n=10;
        System.out.println(solve1(10));
        System.out.println(solve2(10));

    }

    public static int solve1(int n){
        int[] dp=new int[n+1];
        dp[0]=dp[1]=0;
        for(int i=2;i<dp.length;i++){
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }

    public static double solve2(int n){
        int a=n/3;
        int b=n%3;
        if(b==0){
            return Math.pow(3,a);
        }else if(b==1){
            return Math.pow(3,a-1)*4;
        }else {
            return Math.pow(3,a)*2;
        }
    }
}
